package dse;

import java.util.BitSet;
import java.util.List;

public class BloomFilter<T> {
	private int m;
	private BitSet bitset;
	private Hasher<T> hashFunc;
	
	/**
	 * Creates a new, empty, bloom filter.
	 * 
	 * @param m			The size of the bloom filter.  The higher this number
	 * 					the less chance of false positives.
	 * @param hashFunc	The function that takes a key and maps it to a set of
	 * 					bits.  If these bits are on, then the filter indicates 
	 * 					that the key is set.
	 */
	public BloomFilter (int m, Hasher<T> hashFunc) {
		this.m = m;
		this.bitset = new BitSet(m);
		this.hashFunc = hashFunc;
	}
	
	/**
	 * This turns on the bits for the object using the Hasher supplied when the
	 * bloom filter was constructed.  Calls to query with the same object are
	 * guarenteed to work after this.
	 * 
	 * @param object
	 */
	public void add (T key) {
		for (int index : hashFunc.getHashBitsFor(m, key))
			bitset.set(index);
	}
	
	/**
	 * Determines whether or not this object has probably been added to the 
	 * bloom fitler.
	 * 
	 * @param object
	 */
	public boolean query (T key) {
		for (int index : hashFunc.getHashBitsFor(m, key))
			if (bitset.get(index) == false)
				return false;
		return true;
	}
	
	/**
	 * Returns the m (size) that was used to construct this bloom filter.
	 * 
	 * @return
	 */
	public int getM () {
		return m;
	}
	
	/**
	 * Returns an exact copy of this bloom filter.
	 */
	public BloomFilter<T> clone () {
		BloomFilter<T> copy = new BloomFilter<T>(m, hashFunc);
		copy.bitset = (BitSet)this.bitset.clone();
		return copy;
	}
	
	
	
	public interface Hasher<T> {
		List<Integer> getHashBitsFor (int m, T key);
	}
}
